//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2004
//
// Huffman code builder utility.
//

# include "StdAfx.h"
# include "HuffmanCode.h"
# include "fast_log2.h"

void CHuffmanCodeTable::BuildFlat () {
	if (m_cNonEmptyCodes == 0)
		return;

	const size_t cLen = fast_log2 (m_cN);

	for (size_t c = 0; c < m_cN; ++ c) {
		m_pcLen   [c] = cLen;
		m_pdwCode [c] = c;
	}
	m_bFlat = true;
}

void CHuffmanCodeTable::Build () {
	m_bFlat = false;
	if (m_cNonEmptyCodes == 0)
		return;
	if (GetNonEmptyCodes () <= 10000) {
		if (_BuildTree())
			return;
	}
	BuildFlat ();
}

bool CHuffmanCodeTable::_BuildTree () {
	if (m_cNonEmptyCodes == 0)
		return true;

	size_t c;
# ifdef _DEBUG
	// Count all values.
	size_t cValues = 0;
	for (c = 0; c < m_cN; ++ c)
		cValues += m_pcP [c];

	// Estimate the entropy.
	float S = 0;
	float * P = new float [m_cN];
	for (c = 0; c < m_cN; ++ c) {
		if (m_pcP [c] != 0) {
			assert (cValues != 0);
			const float p = float (m_pcP [c])/cValues;
			P [c] = p;
			S += -p*::log (p);
		}
	}
	S /= ::log (2.0);
# endif // _DEBUG

	// Build the binary tree.
	size_t * const pTreeLeft  = new size_t [m_cN*2];
	size_t * const pTreeRight = new size_t [m_cN*2];
	for (c = 0; c < m_cN; ++ c) {
		pTreeLeft  [c] = -1;
		pTreeRight [c] = -1;
	}

	size_t cRootNode = m_cN*2 - 2;
	for (size_t cNode = m_cN; cNode < m_cN*2 - 1; ++ cNode) {
		// Search for 2 least probable values.
		size_t cLP1 = -1;
		for (c = 0; c < cNode; ++ c)
			if (m_pcP [c] != 0) {
				cLP1 = c;
				break;
			}
		for (; c < cNode; ++ c) {
			if (m_pcP [c] == 0)
				continue;
			if (m_pcP [c] < m_pcP [cLP1])
				cLP1 = c;
		}

		size_t cLP2 = -1;
		for (c = 0; c < cNode; ++ c)
			if (m_pcP [c] != 0 && c != cLP1) {
				cLP2 = c;
				break;
			}
		for (; c < cNode; ++ c) {
			if (m_pcP [c] == 0 || c == cLP1)
				continue;
			if (m_pcP [c] < m_pcP [cLP2])
				cLP2 = c;
		}
		if (cLP1 == -1 || cLP2 == -1) {
			cRootNode = cNode - 1;
			break;
		}

		pTreeLeft  [cNode] = cLP1;
		pTreeRight [cNode] = cLP2;
		m_pcP      [cNode] = m_pcP [cLP1] + m_pcP [cLP2];
		m_pcP [cLP1] = 0;
		m_pcP [cLP2] = 0;
	}

	// Assign prefix codes.
	m_c17BitCodes = 0;
	const bool b = _VisitNode (pTreeLeft, pTreeRight, cRootNode, 0, 0);

	delete [] pTreeLeft;
	delete [] pTreeRight;

# ifdef _DEBUG
	if (b) {
		float S2 = 0;
		for (c = 0; c < m_cN; ++ c)
			S2 += P [c]*m_pcLen [c];
		assert ((::fabs(S2 - S) < 1e-3 || 0 <= S2 - S) && S2 - S < 1);

//		InfoMsgBox ("S=%f, S2=%f", S, S2);

		delete [] P;
	}
# endif // _DEBUG
	return b;
}

bool CHuffmanCodeTable::_VisitNode (size_t * _pTreeLeft, size_t * _pTreeRight, size_t _cNode, DWORD _dwCode, size_t _cLen) {
	if (_pTreeLeft [_cNode] == -1) {
		if (_cLen > 16) {
			m_c17BitCodes ++;
			if (m_c17BitCodes > 1024 && m_bCanBeFlat)
				return false;
		}
		assert (_cNode < m_cN);

		// NOTE: leaf reached.
		// Assign the Huffman code to the value.
		assert (_cLen <= 32);
		m_pcLen   [_cNode] = _cLen;
		m_pdwCode [_cNode] = _dwCode;
	} else {
		assert (_cNode < m_cN*2);
		// Visit the branches recursively.
		if (!_VisitNode (_pTreeLeft, _pTreeRight, _pTreeLeft  [_cNode], _dwCode,                  _cLen + 1))
			return false;
		assert (_pTreeRight [_cNode] != -1);
		if (!_VisitNode (_pTreeLeft, _pTreeRight, _pTreeRight [_cNode], _dwCode + (0x1 << _cLen), _cLen + 1))
			return false;
	}
	return true;
}

